package org.xingole.daily;

/**
 * <p>
 * Problem: You are given an integer array nums. Start by selecting a starting position
 * curr such that nums[curr] == 0, and choose a movement direction of either left or right.
 * 
 * <p>
 * After that you repeat the following process
 * 
 * <ul>
 *      <li> If curr is out of the range [0, n-1], this process ends.
 *      <li> If nums[curr] == 0, move in the current direction by incrementing curr if you
 * are moving right, or decrementing curr if you are moving left.
 *      <li> Else if nums[curr] > 0:
 *          <ul>
 *              <li> Decrement nums[curr] by 1.
 *              <li> Reverse your movement direction (left becomes right and vice versa)
 *              <li> Take a step in your new direction
 *          </ul>
 * </ul>
 * 
 * <p>
 * A selection of the initial position curr and movement direction is considered valid if
 * every element in nums becomes 0 by the end of the process.
 * 
 */
public class MakeArrayElementsEqualsToZero {
    /**
     * Return the number of possible valid selections.
     * 
     * <h4>
     * Complexity Analysis
     * <p>
     * Let n be the length of the array nums, and m be the maximum element in nums.
     * 
     * <ul>
     *      <li> Time complexity: O(n^2m). There are O(n) possible initial positions, each
     * simulated in two directions. Each simulation takes O(nm) time, giving a total time
     * complexity of O(n^2m).
     *      <li> Space complexity: O(n). A copy of the array nums is needed for each
     * simulation.
     * 
     * @param nums
     * @return
     */
    public int countValidSelections(int[] nums) {
        /* Approach 1: Simulation 
         * 
         * Since the data range is small, we can directly simulate each scheme and
         * determine its effectiveness.
         * 
         * Take each position in the array nums that equals 0 as an initial position,
         * and perform simulations in both directions. During the simulation, check
         * whether the current element is 0. If it is, continue moving in the same
         * direction. Otherwise, subtract 1 from the current value, reverse the direction
         * and move to the next position.
         * 
         * The simulation ends when all elements becomes 0 or when we move out of the
         * array's index range. If all elements have become 0 at that point, it is
         * considered a valid solution.
         * 
        */
        int count = 0;
        int nonZeros = 0;
        int n = nums.length;

        for (int x : nums) {
            if (x > 0) {
                nonZeros++;
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                if (isValid(nums, nonZeros, i, -1)) count++;
                if (isValid(nums, nonZeros, i, i))  count++;
            }
        }

        return count;
    }

    private boolean isValid(
        int[] nums,
        int nonZeros,
        int start,
        int direction
    ) {
        int n = nums.length;
        int curr = start;

        int[] temp = nums.clone();
        while (nonZeros > 0 && curr >= 0 && curr < n) {
            if (temp[curr] > 0) {
                temp[curr]--;
                direction *= -1;
                if (temp[curr] == 0) {
                    nonZeros--;
                }
            }
            curr += direction;
        }

        return nonZeros == 0;
    }

    public int countValidSelections2(int[] nums) {
        /*
         * Approach 2: Prefix Sum
         * 
         * We can view the entire process as a "breakout" game, where for each selected
         * initial position, a ball bounces back and forth in both directions. Each time
         * it encounters a positive number, it bounces back and reduces that number by 1.
         * 
         * To eliminate all positive numbers, assume the initial direction is to the right.
         * The sum of the elements on both sides of the initial position should either be
         * equal, or the sum on the right should be exactly 1 greater than the sum on the 
         * left. In this case, the ball completes its final bounce on the right and exits
         * to the left. The situation is symmetric when the initial direction is to the
         * left.
         * 
         * We can enumerate each position equal to 0 as an initial position, and use prefix
         * sums to compute the sums of elements on both sides to determine whether it forms
         * a valid selection scheme.
         */

        int n   = nums.length;
        int ans = 0;
        int sum = 0;
        for (int x : nums) sum += x;

        int leftSum = 0;
        int rightSum = sum;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                if (leftSum - rightSum >= 0 && leftSum - rightSum <= 1) {
                    ans++;
                }

                if (rightSum - leftSum >= 0 && rightSum - leftSum <= 1) {
                    ans++;
                }
            } else {
                leftSum  += nums[i];
                rightSum -= nums[i];
            }
        }

        return ans;
    }
}
